class UnionFind:
    def __init__(self, vertices):
        # 初始化并查集
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v in vertices}

    def find(self, vertex):
        # 路径压缩
        if self.parent[vertex] != vertex:
            self.parent[vertex] = self.find(self.parent[vertex])
        return self.parent[vertex]

    def union(self, vertex1, vertex2):
        # 按秩合并
        root1 = self.find(vertex1)
        root2 = self.find(vertex2)

        if root1 != root2:
            if self.rank[root1] > self.rank[root2]:
                self.parent[root2] = root1
            elif self.rank[root1] < self.rank[root2]:
                self.parent[root1] = root2
            else:
                self.parent[root2] = root1
                self.rank[root1] += 1


# 实现一个函数，统计图所有连通分量的个数
# @param： graph-图
def count_connected_components(graph):
    # 将图的所有顶点（即键key的集合）传参，并查集初始化其为一个个集合
    uf = UnionFind(graph.keys())

    # 合并关联的所有顶点
    for v in graph:
        for nei in graph[v]:
            uf.union(v, nei)

    # 将各个连通分量加入集合中
    root_set = set()
    for v in graph:
        root_set.add(uf.find(v))

    # 返回连通分量的个数
    return len(root_set)


# 定义一个图1a的无向图
graph = {
    'a': ['b', 'c'],
    'b': ['a', 'c', 'd'],
    'c': ['a', 'b'],
    'd': ['b'],
    'e': ['f', 'g'],
    'f': ['e'],
    'g': ['f'],
    'h': ['i'],
    'i': ['h'],
    'j': []
}

# 计算连通分量
components = count_connected_components(graph)
print(f"连通分量的数量: {components}")
